package com.leetcode.根据算法进行分类.单调栈相关;

import java.util.ArrayDeque;
import java.util.Arrays;

/**
 * @author: ZhouBert
 * @date: 2021/3/1
 * @description: 581. 最短无序连续子数组
 * https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/
 */
public class B_581_最短无序连续子数组 {

	static B_581_最短无序连续子数组 action = new B_581_最短无序连续子数组();

	public static void main(String[] args) {
//		test1();
		test2();
	}

	public static void test1() {
		// 5
		int[] nums = new int[]{2, 6, 4, 8, 10, 9, 15};
		int res = action.findUnsortedSubarrayByStack(nums);
		System.out.println("res = " + res);
	}

	public static void test2() {
		// 4
		int[] nums = new int[]{1, 3, 2, 2, 2};
		int res = action.findUnsortedSubarrayByStack(nums);
		System.out.println("res = " + res);
	}


	/**
	 * 感觉似乎没有必要用栈来实现
	 * --
	 * 将 nums 进行升序排序，记录下与原数组不同的边界即是变动的地方。
	 * --
	 * 这是个简单明了的方法，但是是 O(nLogN) 的
	 *
	 * @param nums
	 * @return
	 */
	public int findUnsortedSubarray(int[] nums) {
		int len = nums.length;
		int begin = -1, end = 0;
		int[] copyArr = new int[len];
		//将数组进行拷贝
		System.arraycopy(nums, 0, copyArr, 0, len);
		Arrays.sort(copyArr);
		for (int i = 0; i < len; i++) {
			if (nums[i] != copyArr[i]) {
				if (begin != -1) {
					//此时 begin 已经被赋值
					end = i;
				} else {
					begin = i;
				}
			}
		}
		if (begin == -1) {
			return 0;
		}
		return end - begin + 1;
	}

	/**
	 * 通过栈实现的方案
	 * --
	 * PS:如果将栈元素弹出后再塞进去就是 O(n^2)
	 * --
	 * 所以能够摆脱 上面的陷阱完成 的 O(n) 的栈，这个解决方案还是挺厉害的！
	 * 这版有点乱，重新写一个
	 *
	 * @param nums
	 * @return
	 */
	public int findUnsortedSubarrayByStackFail(int[] nums) {
		int len = nums.length;
		ArrayDeque<Integer> deque = new ArrayDeque<>();
		//记录弹出的元素的个数
		int cout = 0;
		int begin = len, end = -1;
		for (int i = 0; i < len; i++) {
			if (deque.isEmpty()) {

			} else {
				if (deque.peekLast() > nums[i]) {
					end = i;
					do {
						deque.removeLast();
						cout++;
					} while (!deque.isEmpty() && deque.peekLast() > nums[i]);
					begin = Math.min(begin, i - cout);
				}
			}
			deque.addLast(nums[i]);
		}
		if (begin == len) {
			return 0;
		}
		return end - begin + 1;
	}

	/**
	 * 使用 栈实现的 单次入栈方案
	 * @param nums
	 * @return
	 */
	public int findUnsortedSubarrayByStack(int[] nums) {
		int len = nums.length;
		ArrayDeque<Integer> deque = new ArrayDeque<>();
		//记录之前遍历的最大的值
		int max = nums[0];
		deque.addLast(max);
		int count = 0, begin = len, end = 0;

		for (int i = 1; i < len; i++) {
			if (max > nums[i]) {
				end = i;
			}
			if (deque.peekLast() > nums[i]) {
				do {
					deque.removeLast();
					count++;
				} while (!deque.isEmpty() && deque.peekLast() > nums[i]);
				begin = Math.min(begin, i - count);

			} else {
				//如果当前元素 大于栈顶元素
				max = Math.max(max, nums[i]);
			}

			deque.addLast(nums[i]);
		}

		if (begin == len) {
			return 0;
		}
		return end - begin + 1;

	}
}
